public class WordDictionary {

    Trie trie;
    public WordDictionary() {
        trie = new Trie();
    }

    public void addWord(String word) {
        char[] str = word.toCharArray();
        Trie newTrie = trie;
        for (int i = 0; i < str.length; i++) {
            int temp = str[i] - 'a';
            if (newTrie.next[temp] == null) newTrie.next[temp] = new Trie();
            newTrie = newTrie.next[temp];
        }
        newTrie.end++;
    }

    public boolean search(String word) {
        Trie newTrie = trie;
        return find(word.toCharArray(), 0, newTrie);
    }

    public boolean find(char[] str, int i, Trie newTrie) {
        if (newTrie == null || newTrie.next == null) return false;
        char c = str[i];
        if (i == str.length - 1) {
            if (c == '.') {
                for (int j = 0; j < 26; j++) {
                    if (newTrie.next[j] != null && newTrie.next[j].end > 0) return true;
                }
                return false;
            } else {
                return newTrie.next[c - 'a'] != null && newTrie.next[c - 'a'].end > 0;
            }
        }
        Trie temp = newTrie;
        if (c == '.') {
            for (int j = 0; j < 26; j++) {
                newTrie = newTrie.next[j];
                if (find(str, i + 1, newTrie)) return true;
                newTrie = temp;
            }
            return false;
        } else {
            newTrie = newTrie.next[c - 'a'];
            return find(str, i + 1, newTrie);
        }
    }
}


